This invention relates to the transformation and selective inverse transformation of very large digital images that may consist of 1,000,000 or more pixels across, and of a potentially unlimited number of lines in length.
With the introduction of commercial one meter resolution satellites, and the need to mosaic multiple very high resolution images together to gain a regional view, the size of images has increased to the point that terabyte (2{circumflex over ( )}40) and larger digital images are becoming common. The term xe2x80x9cdigital imagexe2x80x9d refers to any form of data that can be represented using a two or more dimensional grid. Other types of high volume imagery include seismic surveys and hyperspectal imagery.
The need to transform, compress, transmit and/or store, and then decompress and inversely transform selective areas of such large digital images is an essential requirement in many applications, such as for GIS processing and for reception of imagery from satellites with limited transmission bandwidth and compute power.
Image transformation typically involves one or more steps of filtering that extract characteristics from an image by sifting the image components in a systematic way. In FIG. 1 an original image I(x,y) 10 is filtered in a compound step in which a first filtered image Ixe2x80x2 12 is produced by applying a filter to the image I and a second filtered image Ixe2x80x3 14 is obtained by filtering the image Ixe2x80x2. The image I (and the images Ixe2x80x2 and Ixe2x80x3 ) are illustrated as multi-dimensional arrays of picture elements, called xe2x80x9cpixelsxe2x80x9d. Each pixel represents a correspondingly-located picture element of a visible image that may be observed by the eye. The image I is a two-dimensional array of pixels that is divided into horizontal elements. Each horizontal elementxe2x80x94called a xe2x80x9clinexe2x80x9dxe2x80x94is one pixel high by n pixels long. In FIG. 1, the image 10 includes consecutive lines denoted as L10, L11, L12, L13 and L14 (among others). A pixel 11 is included for illustration in line L10, it being understood that every line is comprised of an equal number of pixels such as the pixel 11. The pixels of the image 10 are digital numbers that represent the magnitudes of elements of visibility such as brightness, color content, and so on. Thus when applied in sequence to a digitally-driven display device, each pixel causes, generation of a spot that is a portion of the image I at a corresponding location. These spots are the visual pixels. that make up the visual image to which the digital image I(x,y) is the counterpart.
The image 10 may be filtered for a number of reasons, for example in order to eliminate one kind of information so that another type of information may be emphasized. Two kinds of filtration are lowpass filtration and highpass filtration. Lowpass filtration reduces or eliminates information above a certain frequency in an image. Highpass filtration does the opposite.
For purposes of illustration, the images 12 and 14 are illustrated in the same format as the image 10, that is they are shown as being comprised of lines of pixels. The pixels of the filtered images 12 and 14 are produced by applying a filter to image pixels. Although the filters are, in practice, complex equations that receive the digital numbers representing pixels and produce digital numbers that are the pixels of the filtered images, it is useful for an understanding of this art to present the filters as discrete apparatuses that can be positioned on and moved with respect to the lines of an image.
Refer now to FIGS. 1 and 1a. A filter 13 is applied to the unfiltered image I(x,y). As represented in FIG. 1a, and by example, the filter 13 could have three components, denoted as a, b, and c. These components are termed xe2x80x9cfilter coefficientsxe2x80x9d, and each is represented in a filter equation by a number. The filter 13 is oriented vertically with respect to the image 10 so that it spans three lines. To filter the image 10, the filter is advanced along the three lines, producing, at each pixel position a filter output in the form of a digital number. The digital number output by the filter 13 is a combination of three products. Each product is obtained by multiplying the value of a coefficient by the digital number of the pixel (P) with which the coefficient is aligned. The combination of products may be arithmetic or algebraic; for example, it may be produced by adding the signed values of the products. Each filter output is the digital number for a pixel in a filtered image. In this example, assume that the filter output Pxe2x80x2 is the digital value for the pixel of the filtered image 12 at the location that corresponds to the pixel aligned with the coefficient b. As the filter 13 is advanced. through the image 10 along the lines that it spans (three in this example), toward the right edge, it produces a line of pixels for the filtered image 12. When the filter 13 reaches the right edge of the image 10, its position is shifted downward (by one line in this example) and it is returned to the left edge of the image 10. Now it is moved (xe2x80x9cscannedxe2x80x9d) from left to right along the lines L12, L13, L14 of the image 10 to produce the next line of pixels for the filtered image 12. In this manner, the image 12 would be produced by scanning the filter 13 along the lines of the image 10 in a sequence from the upper left hand corner of the image in the manner described until the pixel at the lower right-hand corner of the image 10 has been filtered. At the upper and lower edges of the image 10, the filter 13 is positioned so that the coefficient b is aligned with the line at the edge. Along the upper edge, the product produced by the coefficient a would be assigned a predetermined value; similarly, along the lower edge, the product produced by the coefficient c would be assigned a predetermined value.
Assume for illustration that the filtered image Ixe2x80x3 is produced by a filter 15 that has three coefficients and that is oriented, vertically on the image Ixe2x80x2. Assume further that the line L12xe2x80x3 is produced by the filter 15 scanning the three lines L11xe2x80x2, L12xe2x80x2, L13xe2x80x2. In turn, each of these lines is produced by filtering three corresponding lines of the unfiltered image I(x,y). For example, the line L11xe2x80x2 is produced by filtering the lines L10, L11, and L12. Manifestly, in order to produce line L12xe2x80x3, three lines of the image Ixe2x80x2 must be available, that is the lines L11xe2x80x2, L12xe2x80x2 and L13xe2x80x2; in turn, in order to produce these three lines, five lines of the unfiltered image I(x,y) must be availablexe2x80x94the lines L10, L11, L12, L13 and L14. In the prior art, advantage has been taken of this relationship.
FIG. 1 illustrates a prior art compound filter apparatus that is incorporated into the ER Mapper product produced by the assignee of this application. In the prior art compounded filtration apparatus of FIG. 1, the filters 13 and 15 are implemented algorithmically in filter functions 16 and 18. As an input to each filter function (or as an integral component thereof), a buffer is provided that stores only the consecutive image lines of the preceding image that are necessary to perform the filter function. Thus, the buffer 16a needs a capacity of only five lines of the unfiltered image I(x,y), while the buffer 18a needs a capacity of only three lines of the filtered image Ixe2x80x2. Further, the buffers 16a and 18a are managed in real time in such a manner as to reduce the memory requirements for a processor performing the filter functions 16 and 18. Thus, as the unfiltered image I(x,y) is being acquired line-by-line, the buffer 16a is managed as a first inxe2x80x94first out (FIFO) queue to store the five lines of the image 10 that are necessary to produce the three lines of image 12 that will produce the one line of the image 14. Similarly, the buffer 18a is managed as a three-line-deep FIFO queue. Management of the buffers 16a and 18a synchronizes their operations and recursively updates their contents each time a line of the image Ixe2x80x3 is completed. This eliminates the need to accumulate entire images in CPU memory. Instead, as lines are removed from the buffers 16a and 18a and as lines are completed for the image Ixe2x80x3, they are transmitted. In sum, in order to completely filter the image 10, the amount of computer memory space that must be allocated to support the filtering procedure can be computed by totaling the sizes of the buffers required to store the image lines that are currently being processed. For the example of FIG. 1 the total includes the five lines comprising buffer 16a, the three lines comprising the buffer 18a, and the one line of the filtered images Ixe2x80x3 that is currently being produced.
The filters 13 and 15 have been specified for the purposes of illustration only. In fact, digital image processing filters may be constructed as one dimensional arrays that scan multiple pixels of a single line, or as two-dimensional arrays that scan multiple pixels of each of a plurality of lines. Hereinafter, the number of coefficients or taps of a digital filter will be referred to as xe2x80x9cfilter lengthxe2x80x9d or as xe2x80x9cfilter sizexe2x80x9d. Filters of the kind illustrated in FIG. 1 are also referred to as xe2x80x9cspatialxe2x80x9d filters, because the algorithms that produce their results take into account the information contained in a group of spatially related elementsxe2x80x94for example, adjacent pixels.
Image transformation techniques based upon subband image processing have been used in the prior art. In one such technique, a number of xe2x80x9csubbandxe2x80x9d images are created by processing an image, using spatial filters that halve the spatial information content for the image in each grid dimension. This technique is known as discrete wavelet transformation (DWT). For a given image level, one of the subband images contains residual spatial information, which is in turn reduced to a smaller sized set of subband images. This process is continued until the subband images equal the size of the spatial filters being used to produce the subband images. Each subband image can then be compressed by selectively quantizing the subband image and then encoding the quantized subband image. Image compression is achieved by the quantization and encoding stages, following the computation of the DWT.
For very large images, several difficulties arise in the computation of the DWT. The prior art includes methods for computation of the DWT where data representing the entire image is stored in computer memory while the DWT is carried out, or where the computation of the DWT is achieved by dividing the image into a series of tiles, computing the DWT on each tile, and then adding in portions of the DWT from neighboring tiles to result in a seamless DWT.
For very large images, both techniques impose several restrictions that prohibit or limit their use. For example, for a single band eight-bit image of dimensions 1,000,000xc3x971,000,000, the total image size is one terabyte (TB). Assuming a high quality 64-bit floating point-based DWT, storing the entire image in computer memory during transformation would require four TB of computer memory to effect the computation. The prior art tile-based neighborhood add back DWT transformation technique limits overall performance for two reasons. First each tile may have to be stored to slower disk storage and then retrieved to perform the neighbor add back operation, thereby slowing the transform operation. Second, by the need to store intermediate tiles on disk prevents tile-based prior art being used in applications with no disk storage, such as satellites. Some applications, such as continual scanning of the earth using an imagery satellite, allow for only a single sequential pass over the source imagery, rendering the multi-pass tile technique of limited use.
Furthermore, neither technique is well suited to applications which (a) require a guaranteed number of pixels/per second of compression and/or (b) a higher performance rate for compression by taking advantage of multi-CPU computers to carry out the DWT operation in parallel. This is because the prior art structures data in such a way as to be inefficient for multi-CPU operations.
In accordance with the present invention, a method is provided for the seamless wavelet based transformation and selective inverse transformation of very large images.
Accordingly, it is an object of the present invention to provide for the ability to transform images with large widths, and of any length.
A further object of the present invention is to permit performance improvements to be carried out during transformation and/or inverse transformation by the use of multi-CPU computers.
Another object of the present invention is to permit selective inverse transformation of images based on a subset region of interest and based on a subset level of detail.
It is another object of the present invention to provide for the ability to carry out continual real time transmission of compressed imagery in environments such as satellites which have limited computer power and no disk based storage.
To achieve the foregoing objects, the invention is embodied as:
1. A sequential line and level recursive method for computing DWT based transformation on large images without the need for large amounts of computer memory and without the need for intermediate tiles.
2. A method for inverse transforming a subset of the transformed imagery to a subset level of detail.
3. A method for optimizing the computation of image transformation or inverse transformation by applying multi-CPUs to selected stages of the recursive transformation or inverse transformation operation.
4. A method for real time continual transmission of compressed imagery or for storage of compressed images on hard disk.